package problem221;

//221.最大正方形
//https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public int maximalSquare(char[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n+1][m+1];
        int ret = 0;
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(matrix[i-1][j-1] == '1') {
                    int x = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]));
                    x = (int)Math.sqrt(x);
                    dp[i][j] = (x+1)*(x+1);
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        return ret;
    }
}

/**

dp[i][j]: 以(i, j)为右下角的只包含1的矩形的最大面积
 */